package SortAlgorithm;

/**
 * @author zxc
 * @date 2023/01/13 10:02
 **/

import java.util.Random;

/**
 * 题目 ：数组中的第k大元素
 * 题目详述 ：
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
 *
 * 需要注意的是，若是使用堆的思想，来实现寻找数组中的第k大元素也是可以的；
 * 但是，使用最小堆来寻找数组中的第k大元素，所要花费的时间复杂度为O（nlogk）
 * 首先，遍历整个数组，所需要花费的时间复杂度为O（n）；
 * 同时，在遍历过程中，需要对于最小堆中的元素进行删除和插入，在堆中进行元素的插入和删除操作的时间复杂度 : O（logk）；
 * ===》 即，总的时间复杂度为:O（nlogk）；
 */
public class FindKthLargest {
    /**
     * 核心思想：
     * 即，使用快速排序的分区算法的实现 ：不需要对于数组中的所有元素进行排序
     * (实质上，应该成为半排序数组，即pivot之前的元素满足小于pivot；同时pivot之后的元素满足大于/等于pivot;)
     * （遍历整个数组，将小于pivot的所有元素放在前面，同时将大于/等于pivot的所有元素放在后面）
     * 结束条件 ：即，当前pivot所处的位置为n - k，即代表其为当前数组中的第k大元素；
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        int target = nums.length - k; // 即，目标元素在排序数组中的下标;
        // 所要去遍历的主数组nums；
        int start = 0;
        int end = nums.length - 1;
        // 快速排序中分区思想的实现
        // 首先，对于初始数组进行分区实现；（即，等价于给index变量赋予初始值）
        int index = partition(nums , start , end);
        // while循环结束条件 ：直到找到pivot值 == target时，即代表了当前pivot所指向的是，数组中第k大的元素；
        while(index != target){
            // 即，index == target的情况，已经在while循环条件中被考虑了
            // （若是index == target时，则会去跳出循环，代表着已经找到了nums数组中第k大元素）
            if(index < target){
                // 所要求的index在nums数组的后半部分
                start = index + 1;
            }
            else {
                // 所要求的index在nums数组的前半部分
                end = index - 1;
            }
            // 所要求的index，经过上述的if语句判断，可以重新框定所要判断index == target的范围；
            // 等价于，分解成子数组进行判断；
            index = partition(nums , start , end);
        }
        // 当循环结束时，即代表着index == target，同时index也已经指向了数组中第k大元素的下标；
        return nums[index];
    }

    // 快速排序的分区思想的具体实现
    private int partition(int[] nums, int start, int end) {
        // random所代表的当前数组[start,end]中随机下标；
        // 即，通过random下标所指向的nums数组中元素值pivot，来对于正在遍历的数组进行分区；
        int random = new Random().nextInt(end - start + 1) + start;
        // 需要注意的是，new Random().nextInt(value)函数所生成的随机值，其取值范围为；[0 , value)

        // (1)将随机数random所指向的nums数组值pivot 与当前数组（nums数组中，[start,end]范围所指向的子数组num）的尾部元素值nums[end]进行交换；
        swap(nums , random, end);
        // 即，初始化指针p1（其，p1指向的是已经出现过的最后一个小于pivot的值）
        // 由于一开始为开始遍历数组nums，所以p1指针所指向不存在的位置，直到p2指针遍历数组时，遍历到小于pivot的值
        int p1 = start - 1;
        // (2)遍历数组，为p1指针赋予值，即将nums数组进行分区操作。
        // for循环，即类似于p2指针，作用：去遍历整个nums数组，去寻找nums数组中小于pivot的值；
        // 需要注意的话，不会遍历到当前数组的最后一个元素（会在循环外，对于所遍历数组的最后一个元素进行处理）
        for(int i = start ; i < end ; i++){
            if(nums[i] < nums[end]){
                // 由于所要去进行比较的pivot值 为当前数组的尾部元素；
                // 若是在nums数组中寻找到小于pivot的值，即将p1指针前移，同时将p1指针所指向的值与当前正在遍历的值（类似于p2指针指向的值）进行交换；
                p1++;
                swap(nums , p1 , i);
            }
        }
        // 即，当前数组遍历到最后一个元素nums[end] 的时候，需要将pivot从数组尾部转移到其应该出现的位置index
        // index位置，满足在index下标之前的所有元素值都小于pivot（random下标在数组中的值，为pivot），同时在index下标之后的所有元素值都大于/等于pivot
        p1++;
        swap(nums , p1 , end);
        // 由于经过最后一步swap后，当前p1指针所指向的，就是分区之后的位置；
        return p1;
    }

    // 对于数组中指定的两个值进行交换
    private void swap(int[] nums, int value1, int value2) {
        /**
         * 思考 ：为什么只能够通过传入数组下标的方式，来实现数组中元素的交换？
         * 原因 ：
         * 由于Java中只存在值传递，
         * （1）若是直接传入数组值的话，在此函数中对于两个数组值进行交换操作的话，即只会在函数内部生效，即等价于对于真正的nums数组中的元素没有影响；
         * （2）若是传入数组下标，同时传入nums数组引用的话，对于nums数组中的值进行交换操作，则不仅仅不在函数内部生效，而是真正地对于nums数组中的元素进行了位置交换；
         */
        if(value1 != value2){
            // 即，若是所传入的start和end一致的话，即等价于所传入的子数组有且存在一个元素，没必要去进行交换位置
            int temp = nums[value1];
            nums[value1] = nums[value2];
            nums[value2] = temp;
        }
    }

    /**
     * 分析 ：
     * 空间复杂度 ：O（1）；
     * 时间复杂度 ：快速排序的partition函数（作用 ：将数组进行分区，即只需要对于数组进行遍历一遍即可）的时间复杂度 ：O（n）；
     * ===》 总的时间复杂度 ：O（n）；
     *
     * 对比之下 ：堆方法所实现的空间复杂度 ：O（k）；（k，为堆的大小）
     * 堆方法所实现的时间复杂度 ：O（nlogk）；
     */
}
